#include<stdio.h>
#include<string.h>
#include "des.h"

#define I(a) 63-a //(63-(56-a/8*8+a%8))

ll printHex(ll);

int get(Data,int);
void set(Data*,int,int);

void permute(Data,const Table,const int,Data*);
const int ip_tbl[] = {  58,50,42,34,26,18,10, 2,
                        60,52,44,36,28,20,12, 4,
                        62,54,46,38,30,22,14, 6,
                        64,56,48,40,32,24,16, 8,
                        57,49,41,33,25,17, 9, 1,
                        59,51,43,35,27,19,11, 3,
                        61,53,45,37,29,21,13, 5,
                        63,55,47,39,31,23,15, 7
                     };
void permuteIP(Data,Data*);
const int ip_rtbl[] = { 40, 8,48,16,56,24,64,32,
                        39, 7,47,15,55,23,63,31,
                        38, 6,46,14,54,22,62,30,
                        37, 5,45,13,53,21,61,29,
                        36, 4,44,12,52,20,60,28,
                        35, 3,43,11,51,19,59,27,
                        34, 2,42,10,50,18,58,26,
                        33, 1,41, 9,49,17,57,25
                      };
void permuteRIP(Data,Data*);
const int pc1_tbl[] = { 57,49,41,33,25,17, 9,
                        1,58,50,42,34,26,18,
                        10, 2,59,51,43,35,27,
                        19,11, 3,60,52,44,36,
                        63,55,47,39,31,23,15,
                        7,62,54,46,38,30,22,
                        14, 6,61,53,45,37,29,
                        21,13, 5,28,20,12, 4
                      };
const int pc2_tbl[] = { 14,17,11,24, 1, 5,
                        3,28,15, 6,21,10,
                        23,19,12, 4,26, 8,
                        16, 7,27,20,13, 2,
                        41,52,31,37,47,55,
                        30,40,51,45,33,48,
                        44,49,39,56,34,53,
                        46,42,50,36,29,32
                      };

void generateSubKey(const Key, Key*);
void T(Data data,const Key key,Data *output);
const int e_tbl[] = {   32, 1, 2, 3, 4, 5,
                        4, 5, 6, 7, 8, 9,
                        8, 9,10,11,12,13,
                        12,13,14, 15, 16, 17,
                        16,17,18, 19, 20, 21,
                        20,21,22, 23, 24, 25,
                        24,25,26, 27, 28, 29,
                        28,29,30, 31, 32, 1
                    };
const int s_tbl[8][64] = {
    {
        14,  4, 13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7,
        0, 15,  7,  4, 14,  2, 13,  1, 10,  6, 12, 11,  9,  5,  3,  8,
        4,  1, 14,  8, 13,  6,  2, 11, 15, 12,  9,  7,  3, 10,  5,  0,
        15, 12,  8,  2,  4,  9,  1,  7,  5, 11,  3, 14, 10,  0,  6, 13
    },
    {
        15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10,
        3, 13,  4,  7, 15,  2,  8, 14, 12,  0,  1, 10,  6,  9, 11,  5,
        0, 14,  7, 11, 10,  4, 13,  1,  5,  8, 12,  6,  9,  3,  2, 15,
        13,  8, 10,  1,  3, 15,  4,  2, 11,  6,  7, 12,  0,  5, 14,  9
    },
    {
        10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8,
        13,  7,  0,  9,  3,  4,  6, 10,  2,  8,  5, 14, 12, 11, 15,  1,
        13,  6,  4,  9,  8, 15,  3,  0, 11,  1,  2, 12,  5, 10, 14,  7,
        1, 10, 13,  0,  6,  9,  8,  7,  4, 15, 14,  3, 11,  5,  2, 12
    },
    {
        7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15,
        13,  8, 11,  5,  6, 15,  0,  3,  4,  7,  2, 12,  1, 10, 14,  9,
        10,  6,  9,  0, 12, 11,  7, 13, 15,  1,  3, 14,  5,  2,  8,  4,
        3, 15,  0,  6, 10,  1, 13,  8,  9,  4,  5, 11, 12,  7,  2, 14
    },
    {
        2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9,
        14, 11,  2, 12,  4,  7, 13,  1,  5,  0, 15, 10,  3,  9,  8,  6,
        4,  2,  1, 11, 10, 13,  7,  8, 15,  9, 12,  5,  6,  3,  0, 14,
        11,  8, 12,  7,  1, 14,  2, 13,  6, 15,  0,  9, 10,  4,  5,  3
    },
    {
        12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11,
        10, 15,  4,  2,  7, 12,  9,  5,  6,  1, 13, 14,  0, 11,  3,  8,
        9, 14, 15,  5,  2,  8, 12,  3,  7,  0,  4, 10,  1, 13, 11,  6,
        4,  3,  2, 12,  9,  5, 15, 10, 11, 14,  1,  7,  6,  0,  8, 13
    },
    {
        4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1,
        13,  0, 11,  7,  4,  9,  1, 10, 14,  3,  5, 12,  2, 15,  8,  6,
        1,  4, 11, 13, 12,  3,  7, 14, 10, 15,  6,  8,  0,  5,  9,  2,
        6, 11, 13,  8,  1,  4, 10,  7,  9,  5,  0, 15, 14,  2,  3, 12
    },
    {
        13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7,
        1, 15, 13,  8, 10,  3,  7,  4, 12,  5,  6, 11,  0, 14,  9,  2,
        7, 11,  4,  1,  9, 12, 14,  2,  0,  6, 10, 13, 15,  3,  5,  8,
        2,  1, 14,  7,  4, 10,  8, 13, 15, 12,  9,  0,  3,  5,  6, 11
    }
};
const int p_tbl[] = {
    16,  7,   20,  21,
    29,  12,  28,  17,
    1,   15,  23,  26,
    5,   18,  31,  10,
    2,   8,   24,  14,
    32,  27,  3,   9,
    19,  13,  30,  6,
    22,  11,  4,  25
};
ll printHex(ll a) {
    ll hex = 0ll, temp;
    int i;
    for (i = 0; i<16; i++) {
        temp = (get(a,0 + i * 4)<<3) + (get(a,1 + i * 4)<<2) + (get(a,2 + i * 4)<<1) + get(a,3 + i * 4);
        hex = hex*16+temp;
    }
    return hex;
}
void printBinary(ll a){
    int i = 0;
    for(i = 0 ; i < 64 ; i++)
        printf("%d",get(a,i));
    printf("\n");
}
int get(Data d, int index) {
    return (d>>I(index)) & 1;
}
void set(Data *d, int index, int value) {
    *d &= ~(1ll<<I(index));
    *d |= (((Data)value)<<I(index));
}

void permute(Data input,const Table table,const int bits,Data *output) {
    *output = 0ll;
    int i;
    for(i = 0 ; i < bits ; i++)
        set(output,i,get(input,table[i]-1));
}
void permuteIP(Data input,Data *output) {
    permute(input,(Table)ip_tbl,64,output);
}
void permuteRIP(Data input,Data *output) {
    permute(input,(Table)ip_rtbl,64,output);
}
void LS1(Key *key, int lr) {
    int temp = get(*key,0+lr*28), i;
    for(i = 0 + lr*28 ; i < 27 + lr*28 ; i++)
        set(key,i,get(*key,i+1));
    set(key,27+lr*28,temp);
}
void LS(int i,Key *key,int lr) {
    LS1(key,lr);
    if(i==1 || i==2 || i==9 || i==16)
        return;
    else
        LS1(key,lr);
}
void generateSubKey(const Key key, Key* sub_key) {
    Key temp;
    //(1) 实行置换 PC-1，得到 C0 D0
    permute(key,(Table)pc1_tbl,56,&temp);
    //16份子密钥生成
    int i;
    for(i = 1 ; i <= 16 ; i++) {
        //(2) 计算 Ci = LS(Ci-1) 和 Di = LS(Di-1)
        LS(i,&temp,0);
        LS(i,&temp,1);
        //(3) 对56位的 Ci Di压缩后实行 PC-2 置换
        permute(temp,(Table)pc2_tbl,48,&sub_key[i-1]);
    }
}
void f(Data R,const Key K,Data *output) {
    Data temp = 0ll;
    //(1) 作 E-扩展
    permute(R,(Table)e_tbl,48,output);
    //(2) 将 E(Ri-1) 和长度为48位的子密钥 Ki 作48位二进制串按位异或运算，Ki 由密钥 K 生成；
    int i,j;
    for(i = 0 ; i < 48 ; i++) {
        set(output,i,get(*output,i) ^ get(K,i));
    }
    //(3) 将 (2) 得到的结果平均分成8个分组，每个分组长度6位。各个分组分别经过8个不同的 S-盒进行 6-4 转换，得到8个长度分别为4位的分组；
    for(i = 0 ; i < 8 ; i++) {
        int a = (get(*output,0+i*6)<<1) + get(*output,5+i*6);
        int b = (get(*output,1+i*6)<<3)+(get(*output,2+i*6)<<2)+(get(*output,3+i*6)<<1)+get(*output,4+i*6);
        a = s_tbl[i][a*16+b];
        //(4) 将 (3) 得到的分组结果顺序连接得到长度为32位的串；
        for(j = 0 ; j < 4 ; j++) {
            b = a & 1;
            a = a >> 1;
            set(&temp,i*4+3-j,b);
        }
    }
    //(5) 将 (4) 的结果经过 P-置换，得到的结果作为轮函数 f(Ri-1, Ki) 的最终32位输出。
    permute(temp,(Table)p_tbl,32,output);
}
void T(Data data,const Key key,Data *output) {
    Data high = 0ll;
    int i;
    for(i = 0 ; i < 32 ; i++)
        set(&high,i,get(data,32+i)); // high = (data & ((1ll<<32)-1ll)) << 32;
    f(high, key, output);
    for(i = 0 ; i < 32 ; i++) {
        set(output,32+i,get(*output,i)^get(data,i));
        set(output,i,get(high,i));
    }
}
void mydes(Data input,const Key key,Data *output,int work) {
    Key sub_key[16];
    //生成16组子密钥
    generateSubKey(key,(Key*)sub_key);
    //置换 IP,生成L0 R0
    permuteIP(input,output);
    //迭代序列 T
    int i;
    for(i = 0 ; i < 16 ; i++) {
        if(work) T(*output,sub_key[15-i],output);
        else T(*output,sub_key[i],output);
    }
    //交换置换 WW
    Data low = *output & ((1ll<<32)-1);
    *output = (*output>>32) & ((1ll<<32)-1);
    *output |= low<<32;
    //逆置换 IP-1
    permuteRIP(*output,output);
}

/*base64*/
const unsigned char base64_table[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/="; 
int base64_encode(const unsigned char *str,unsigned char *base64str){
    int len = strlen(str), rlen = len%3, i, count=0;
    len = (len-rlen);
    for(i = 0 ; i < len/3 ; i++){
        base64str[count++] = str[i*3] >> 2;
        base64str[count++] = ((str[i*3] & 3) << 4) | (str[i*3+1] >> 4);
        base64str[count++] = ((str[i*3+1] & 15) << 2) | (str[i*3+2] >> 6);
        base64str[count++] = str[i*3+2] & 63;
        if(count % 76 == 0)
            base64str[count++] = '\n';
    }
    if(rlen--){
        base64str[count++] = str[i*3] >> 2;
        if(rlen == 1){
            base64str[count++] = ((str[i*3] & 3) << 4) | (str[i*3+1] >> 4);
            base64str[count++] = ((str[i*3+1] & 15) << 2) | 0;
            base64str[count++] = 64;
        }
        else{
            base64str[count++] = ((str[i*3] & 3) << 4) | 0;
            base64str[count++] = 64;
            base64str[count++] = 64;
        }
    }
    base64str[count] = '\0';
    return count;
}
void base64_decode(const unsigned char *base64str,unsigned char *str){
    int len = strlen(base64str), padding = 0,i,count=0;
    if(base64str[len-1] == '=') padding++;
    if(base64str[len-2] == '=') padding++;
    for(i = 0 ; i < len/4; i++){
        str[i*3]    = (base64str[count]<<2) | (base64str[++count]>>4);
        str[i*3+1]  = (base64str[count]<<4) | (base64str[++count]>>2);
        str[i*3+2]  = (base64str[count]<<6) | base64str[++count];
        if(count % 76 == 75)
            ++count;
    }
    str[i*3-padding] = '\0';
}
void translateBase64(const unsigned char *base64str,int len){
    int i;
    for(i = 0 ; i < len ; i++){
        printf("%c",base64_table[base64str[i]]);
    }
}
void printBase64(const unsigned char *str){
    unsigned char base64str[200];
    int len = base64_encode(str,base64str);
    translateBase64(base64str,len);
}
void toData(const char* block, Data *d,int len){
    char buf[9];
    int i; 
    for(i=0;i<len&&i<8;i++) buf[i]=block[i];
    i=8-len;
    while(len < 8) buf[len++]=i;
    ll temp = *((ll*)buf);
    for(i=0;i<64;i++)
        set(d,i,(temp>>(63-(56-i/8*8+i%8))) & 1);
}
void printData(Data d,char* buf){
    ll* temp = (ll*)buf;int i,j;
    for(i=0;i<64;i++)
        set(temp,56-i/8*8+i%8,get(d,i));
    for(i=buf[7],j=1;j<i;j++)
        if(buf[7-j]!=i) i=0;
    if(!!i) for(i=buf[7],j=0;j<i;j++) buf[7-j]='\0';
    buf[8] = '\0';

    // printf("\n");
    // ll temp2 = *((ll*)buf);
    // printf("%08x%08x\n",temp2>>32,temp2);
}
int des(const char *k, const char *msg, int len, char *output){
#if DEBUG
    memcpy(output,msg,(len+1)*sizeof(char));
    return len;
#else
    char input[200];
    memcpy(input,msg,(len+1)*sizeof(char));
    Key key; toData(k,(Data*)&key,strlen(k));
    Data data,encoded;
    int loop = len/8+1, i;
    for(i = 0 ; i < loop ; i++){
        toData(&input[8*i],&data,len-i*8);
        // printf("%08x%08x->",data>>32,data);
        mydes(data,key, &encoded,0);
        // printf("%08x%08x\n",encoded>>32,encoded);
        printData(encoded,&output[8*i]);
    }
    output[loop*64] = '\0';
    return loop*8;
    // printf("(%ld,%ld)",strlen(msg),strlen(output));
#endif
}
void rdes(const char *k, const char *msg, int len, char *output){
#if DEBUG
    memcpy(output,msg,(len+1)*sizeof(char));
#else
    char input[200];
    memcpy(input,msg,(len+1)*sizeof(char));
    Key key; toData(k,(Data*)&key,strlen(k));
    Data data,decoded;
    int loop = len/8, i;
    for(i = 0 ; i < loop ; i++){
        toData(&input[8*i],&data,len-i*8);
        // printf("%08x%08x->",data>>32,data);
        mydes(data,key, &decoded,1);
        // printf("%08x%08x\n",decoded>>32,decoded);
        printData(decoded,&output[8*i]);
    }
    output[loop*64] = '\0';
    // printf("(%ld,%ld)",strlen(msg),strlen(output));
#endif
}
